#!/usr/bin/env python3
# coding: utf-8

import random, copy


word_size = 32

class Hashtable(object):
    def __init__(self, *,
                 r=2,
                 a=random.randint(2 ** (word_size - 1), 2 ** word_size),
                 get_key=lambda x: x):
        self._table = [[] for i in range(2 ** r)]
        self._a = a
        self._r = r
        self._get_key = get_key

    def __str__(self):
        return '\n'.join([str(row) for row in self._table])

    def _hash(self, x):
        return (self._a * self._get_key(x) % 2 ** word_size) >> (word_size - self._r)  # too much overhead

    def get_index(self, x, cell):
        key = self._get_key(x)
        for i in range(len(cell)):
            if key == self._get_key(cell[i]):
                return i
        return None

    def insert(self, data):
        cell = self._table[self._hash(data)]
        if self.get_index(data, cell) is None:
            cell.append(data)
            return True
        return False

    def delete(self, data):
        cell = self._table[self._hash(data)]
        i = self.get_index(data, cell)
        if i is not None:
            del cell[i]
            return True
        return False

    def find(self, data):
        h = self._hash(data)
        cell = self._table[h]
        return cell[self.get_index(data, cell)]
